package com.fr.lintcode;

import org.junit.Test;

/**
 * @author 付荣
 * @version 创建时间：2019年3月7日 下午2:50:23
 */
public class Q3 {
	 /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
	
	//TODO
    public int digitCounts(int k, int n) {
    	if(n < 10){
    		if(n >= k){
    			return 1;
    		}
    		return 0;
    	}
    	int sum = 0;
    	if(k == 0){
    		while(n > 0){
    			sum += n/10;
    			n=n/10;
    		}
    		return sum + 1;
    	}
    	
    	int t = 1;
        while(n >= t){
        	int t1 = t * 10;
        	sum = sum + (n/t1) * t;
        	int temp = n % t1;
        	int now = temp / t;
        	if(now > k){
        		sum = sum + t;
        	}else if(now == k){
        		int temp1 = temp % t;
        		sum = sum + temp1 + 1;
        	}
        	t = t1;
        }
        return sum;
    }
    public int digitCounts1(int k, int n) {
    	int sum = 0;
        for(int i = 0; i <= n; i ++){
        	int j = i;
        	while(j > 0){
        		int temp = j % 10;
        		if (temp == k){
        			sum ++;
        		}
        		j /= 10;
        	}
        }
        return sum;
    }
    @Test
    public void testA(){
    	System.out.println(digitCounts(1,10));
    	System.out.println(digitCounts1(1,10));
    }
}
